#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    vector<int> ret;
    vector<int> index;
    int indexTemp[500010];
    int numsTemp[500010];
    vector<int> countSmaller(vector<int>& nums) {
        ret.resize(nums.size());
        index.resize(nums.size());
        for (int i = 0; i < nums.size(); i++)
        {
            index[i] = i;
            ret[i] = 0;
        }

        mergesort(nums, 0, nums.size() - 1);
        return ret;
    }

    void mergesort(vector<int> nums, int left, int right)
    {
        if (left >= right)
            return;

        int mid = (left + right) >> 1;

        mergesort(nums, left, mid);
        mergesort(nums, mid + 1, right);

        int i = 0;
        int cur1 = left, cur2 = mid + 1;
        while (cur1 <= mid && cur2 <= right)
        {
            if (nums[cur1] <= nums[cur2])
            {
                numsTemp[i] = nums[cur2];
                indexTemp[i++] = index[cur2++];
            }
            else
            {
                ret[index[cur1]] += right - cur2 + 1;
                numsTemp[i] = nums[cur1];
                indexTemp[i++] = index[cur1++];
            }
        }
        while (cur1 <= mid)
        {
            numsTemp[i] = nums[cur1];
            indexTemp[i++] = index[cur1++];
        }
        while (cur2 <= right)
        {
            numsTemp[i] = nums[cur2];
            indexTemp[i++] = index[cur2++];
        }

        for (int i = left;i <= right;i++)
        {
            nums[i] = numsTemp[i - left];
            index[i] = indexTemp[i - left];
        }
    }
};

int main()
{
    vector<int> nums;
    nums.push_back(0);
    nums.push_back(1);
    nums.push_back(2);

    Solution s;
    s.countSmaller(nums);
    return 0;
}